UVa/12315 - The Starflyer Agents/12315.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 #define dassert(x) if (false) { assert(x); }
  28
  29 struct node {
  30     string label;
  31     vector<node> sons;
  32     node() { }
  33     node(const string &lbl) : label(lbl) { }
  34     bool isVariable() {
  35         dassert(label.size() > 0);
  36         return sons.size() == 0 and isupper(label[0]);
  37     }
  38     bool isConstant() {
  39         dassert(label.size() > 0);
  40         return sons.size() == 0 and islower(label[0]);
  41     }
  42     bool isFunction() {
  43         dassert(label.size() > 0);
  44         if (sons.size() == 0) dassert(islower(label[0]));
  45         return sons.size() > 0;
  46     }
  47 };
  48
  49
  50 node parse(const string &s, int i, int j) {
  51     if (s[j] != ')') { // constant or variable
  52         return node(s.substr(i, j - i + 1));
  53     }
  54     dassert(s[j] == ')');
  55
  56     int k = i; while (s[k] != '(') k++;
  57     node ans = node(s.substr(i, k - i));
  58     // split string from [k+1, j-1]
  59     int balance = 0;
  60     for (i = k + 1; i < j; ) {
  61         k = i;
  62         while (k <= j) {
  63             if (s[k] == ')') balance--;
  64             if (s[k] == '(') balance++;
  65             if (k == j or s[k] == ',' and balance == 0) {
  66                 node son = parse(s, i, k - 1);
  67                 ans.sons.push_back(son);
  68                 break;
  69             }
  70             k++;
  71         }
  72         i = k + 1;
  73     }
  74     dassert(i == j + 1);
  75     return ans;
  76 }
  77
  78 void print(const node &t, int depth = 0) {
  79     for (int i = 0; i < depth; ++i) printf(" ");
  80     printf("%s\n", t.label.c_str());
  81     for (int i = 0; i < t.sons.size(); ++i) {
  82         print(t.sons[i], depth + 1);
  83     }
  84 }
  85
  86
  87 map<string, node> mapping;
  88
  89 bool contains(node r, const string &variable, int depth = 0) {
  90     while (r.isVariable() and mapping.count(r.label) > 0) r = mapping[r.label];
  91     if (r.label == variable) return true;
  92     for (int i = 0; i < r.sons.size(); ++i) {
  93         if (contains(r.sons[i], variable, depth + 1)) return true;
  94     }
  95     return false;
  96 }
  97
  98
  99 bool unify(const node &A, const node &B, int depth = 0) {
 100     //if (depth > 4) return false; // Remove this and you'll get a runtime error. Change for depth > 4 and you'll get a runtime error too.
 101     node a = A, b = B;
 102     while (a.isVariable() and mapping.count(a.label) > 0) {
 103         a = mapping[a.label];
 104     }
 105     while (b.isVariable() and mapping.count(b.label) > 0) {
 106         b = mapping[b.label];
 107     }
 108
 109     if (a.isConstant()) {
 110         if (b.isFunction()) return false;
 111         if (b.isConstant()) {
 112             if (a.label == b.label) return true;
 113             else return false;
 114         }
 115     }
 116
 117     if (b.isConstant()) {
 118         if (a.isFunction()) return false;
 119         if (a.isConstant()) {
 120             if (a.label == b.label) return true;
 121             else return false;
 122         }
 123     }
 124
 125     if (a.isVariable() and b.isVariable()) {
 126         if (a.label == b.label) return true;
 127         else {
 128             mapping[a.label] = b;
 129             return true;
 130         }
 131     }
 132
 133     if (a.isVariable()) {
 134         dassert(!b.isVariable());
 135         if (contains(b, a.label)) return false;
 136         else {
 137             mapping[a.label] = b;
 138             return true;
 139         }
 140     }
 141
 142     if (b.isVariable()){
 143         dassert(!a.isVariable());
 144         if (contains(a, b.label)) return false;
 145         else {
 146             mapping[b.label] = a;
 147             return true;
 148         }
 149     }
 150
 151     // both are functions
 152     dassert(a.isFunction() and b.isFunction());
 153     if (a.label != b.label) return false;
 154     if (a.sons.size() != b.sons.size()) return false;
 155     for (int i = 0; i < a.sons.size(); ++i) {
 156         bool r = unify(a.sons[i], b.sons[i], depth + 1);
 157         if (!r) return false;
 158     }
 159     return true;
 160 }
 161
 162 int main(){
 163     string s = "f(X,g(c))";
 164     // s = "f(f(Y),Z)";
 165     // s = "f(c,g(Y,d))";
 166     // s = "f(f(a),a)";
 167     // s = "f(f(f(X,a),a),a)";
 168     // s = "f(f(f(f(f(f(f(f(f(f(f(X)),d)))),e,f,g(c,c))))),a,a,a,a,a)";
 169     // s = "f(f(f(f(f(f(f(f(f(f(f(X)),d)))),e,f,g(c,c))))),a,a,a,a,a,f(f(f(f(f(a,n,d,y,m,e,j,i,a,f(f(f(f(f(f(X))))))))))))";
 170     // s = "X";
 171     // s = "a";
 172     // s = "x";
 173     //node t = parse(s, 0, s.size() - 1);
 174     //print(t);
 175     string name; int n;
 176     while (cin >> name >> n) {
 177         if (name == "END" and n == 0) break;
 178         vector<node> trees(n);
 179         for (int i = 0; i < n; ++i) {
 180             string expression; cin >> expression;
 181             trees[i] = parse(expression, 0, expression.size() - 1);
 182         }
 183         mapping.clear();
 184         bool works = true;
 185         for (int i = 0; i < n - 1 and works; ++i) {
 186             works &= unify(trees[i], trees[i+1]);
 187         }
 188         if (works) {
 189             printf("analysis inconclusive on %s\n", name.c_str());
 190         } else {
 191             printf("%s is a Starflyer agent\n", name.c_str());
 192         }
 193     }
 194     return 0;
 195 }